package algorithm.array;

import util.GsonUtil;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * leetcode : https://leetcode.com/problems/pascals-triangle-ii/description/
 * 119. Pascal's Triangle II
 * Difficulty : Easy
 *
 * 给定一个k, k<=33 求在杨辉三角中第k层的结果.
 * 要求用 O(k) 空间复杂度
 * k从0开始，所以举栗：
 * k=3
 * [1,3,3,1]
 *
 * 思路：
 * 只要知道三角元素的计算方式，新建一个k个大小的列表，里面初始化值为1
 * @Author Antony
 * @Since 2018/8/3 14:39
 */
public class PascalsTriangleII {

    public static void main(String[] args) {
        int k = 4;
        System.out.println(GsonUtil.toJson(getRow(k)));
    }


    /**
     * beats 86.21%
     * 注意：
     * 题目要求k从0开始，所以新建的数组长度大小应当是k+1
     */
    public static List<Integer> getRow(int rowIndex) {
        Integer[] arr = new Integer[rowIndex+1];
        for(int i=0; i<=rowIndex; i++){
            arr[i] = 1;
            int tmpIdx = i;
            while(tmpIdx > 1){
                tmpIdx--;
                arr[tmpIdx] = arr[tmpIdx-1] + arr[tmpIdx];
            }
        }
        return Arrays.asList(arr);
    }
}
